package cn.ldw.test;

import java.util.HashMap;

public class Node {
    public int key, val;
    public Node prev, next;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

class DoubleList {
    Node head;
    Node tail;
    int size;

    public void addFirst(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        size++;
    }

    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    public Node removeLast() {
        Node res = tail.prev;
        remove(tail.prev);
        return res;
    }
    public int size() {
        return size;
    }
}

class LRUCache {
    private int capacity;
    DoubleList list;
    HashMap<Integer, Node> map;
    public LRUCache(int cap) {
        this.capacity = cap;
        list = new DoubleList();
        map = new HashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        int res = map.get(key).val;
        put(key, res);
        return res;
    }


    public void put(int key, int val) {
        Node node = new Node(key, val);
        if(map.containsKey(key)) {
            list.remove(map.get(key));
            list.addFirst(node);
            map.put(key, node);
        }
        else {
            if(capacity == list.size) {
                Node last = list.removeLast();
                map.remove(last.key);
            }
            list.addFirst(node);
            map.put(key, node);
        }
    }
}
